package sol.leetcode;

import java.util.*;

/**
 * Combination Sum
 */
public class Issue039 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        find(candidates, 0, target, res, new ArrayList<Integer>());
        return res;
    }

    //已经找到了prefix，从from位置往后查找能得到remain的组合
    public void find(int[] candidates, int from, int remain, List<List<Integer>> res, List<Integer> prefix) {
        if (remain < 0)
            return;
        if (remain == 0) {
            res.add(prefix);
            return;
        }
        for (int i = from; i < candidates.length; ++i) {
            List<Integer> newPrefix = new ArrayList<Integer>(prefix);
            int num = candidates[i];
            newPrefix.add(num);
            find(candidates, i, remain - num, res, newPrefix);
        }
    }

    public static void main(String[] args) {
        int[] candidates = {8, 7, 4, 3};
        int target = 11;
        List<List<Integer>> res = new Issue039().combinationSum(candidates, target);
        for (List<Integer> r : res)
            System.out.println(r);

    }
}
